//https://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=13&tqId=23453&ru=%2Fpractice%2F947f6eb80d944a84850b0538bf0ec3a5&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//题目：1.典型层序遍历题目；广度优先遍历；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    //层次遍历
    vector<vector<int> > Print(TreeNode* pRoot) {
        TreeNode* head = pRoot;
        vector<vector<int> > res;
        if(head == NULL)
            //如果是空，则直接返回空数组
            return res;
        //队列存储，进行层次遍历
        queue<TreeNode*> temp;
        temp.push(head);
        TreeNode* p;
        while(!temp.empty()){
            //记录二叉树的某一行
            vector<int> row; 
            int n = temp.size();
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                p = temp.front();
                temp.pop();
                row.push_back(p->val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(p->left)
                    temp.push(p->left);
                if(p->right)
                    temp.push(p->right);
            }
            res.push_back(row);
        }
        return res;
    }
};